package data_structures_and_algorithms.recursion_traceback.learn;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.*;


/**
 * @ClassName Code_note_02_printAll_Permutation
 * @Description: TODO
 * @Author: myl
 * @create_time: 2022/10/31 00:48
 */
public class Code_note_02_printAll_Permutation {

    public static class PrintAllPermutation{
        public static void main(String[] args) {
            String string = "aca";
            System.out.println(Arrays.toString(getAllPermutation(string).toArray()));

        }

        static List<String> ans = new LinkedList<>();
        public static List<String> getAllPermutation(String string){
            if (string == null || string.length() == 0){
                return new ArrayList<>();
            }
            char[] chars = string.toCharArray();
            process(chars, 0, new StringBuilder());

            return ans;
        }

        private static void process(char[] chars, int index, StringBuilder stringBuilder) {
            // 判断是否到达末尾
            if (index == chars.length){
                ans.add(stringBuilder.toString());
                return;
            }

            // 转换状态继续递归
            for (int i = index; i < chars.length; i++) {
                swap(chars, i, index);
                stringBuilder.append(chars[index]);
                process(chars, index + 1, stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                swap(chars, i, index);
            }
        }

        private static void swap(char[] chars, int i, int index) {
            char temp = chars[index];
            chars[index] = chars[i];
            chars[i] = temp;
        }
    }


    // 分支限界
    public static class PrintAllPermutationWithNoRepeatVersionSet{
        public static void main(String[] args) {
            String string = "aaca";
            System.out.println(Arrays.toString(getAllPermutation(string).toArray()));

        }

        static List<String> ans = new LinkedList<>();
        public static List<String> getAllPermutation(String string){
            if (string == null || string.length() == 0){
                return new ArrayList<>();
            }
            char[] chars = string.toCharArray();
            process(chars, 0, new StringBuilder());

            return ans;
        }

        private static void process(char[] chars, int index, StringBuilder stringBuilder) {
            // 判断是否到达末尾
            if (index == chars.length){
                ans.add(stringBuilder.toString());
                return;
            }

            // 转换状态继续递归，记录当前层使用过的字符
            boolean[] visited = new boolean[26];// 相对节省一点空间
            for (int i = index; i < chars.length; i++) {
                if (visited[chars[i] - 'a']){
                    continue;
                }
                visited[chars[i] - 'a'] = true;
                swap(chars, i, index);
                stringBuilder.append(chars[index]);
                process(chars, index + 1, stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                swap(chars, i, index);
            }
        }

        private static void swap(char[] chars, int i, int index) {
            char temp = chars[index];
            chars[index] = chars[i];
            chars[i] = temp;
        }
    }



    public static class PrintAllPermutationWithNoRepeatVersionSort{
        public static void main(String[] args) {
            String string = "aaca";
            System.out.println(Arrays.toString(getAllPermutation(string).toArray()));

        }

        static List<String> ans = new LinkedList<>();
        public static List<String> getAllPermutation(String string){
            if (string == null || string.length() == 0){
                return new ArrayList<>();
            }
            char[] chars = string.toCharArray();
            Arrays.sort(chars);
            process(chars, 0, new StringBuilder());

            return ans;
        }

        private static void process(char[] chars, int index, StringBuilder stringBuilder) {
            // 判断是否到达末尾
            if (index == chars.length){
                ans.add(stringBuilder.toString());
                return;
            }

            // 转换状态继续递归，记录当前层使用过的字符
            for (int i = index; i < chars.length; i++) {
                if (i != index && chars[i] == chars[index]){
                    continue;
                }
                swap(chars, i, index);
                stringBuilder.append(chars[index]);
                process(chars, index + 1, stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                swap(chars, i, index);
            }
        }

        private static void swap(char[] chars, int i, int index) {
            char temp = chars[index];
            chars[index] = chars[i];
            chars[i] = temp;
        }
    }

}
